/**
 * @author: lk
 * @data: 2021/11/10 16:52
 */
package w6_c1_quicksort;

import selectionSort.ArrayGenerator;
import selectionSort.SortingHelper;

import java.util.Arrays;
import java.util.Random;


/**
 * 快速排序算法。
 *
 * @param <E>
 */
public class QuickSort<E extends Comparable<E>> {
    /**
     * 单路快速排序算法。partition的操作是：arr(l,j]小于pivot, arr(j,i)>pivot .只有i从l+1遍历到h。
     * 若数组元素都相同，退化为O(n^2)
     *
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        Random rnd = new Random();
        sortHelper(arr, 0, arr.length - 1, rnd);
    }

    /**
     * 单路快排实现
     *
     * @param arr
     * @param l
     * @param h
     * @param rnd
     * @param <E>
     */
    private static <E extends Comparable<E>> void sortHelper(E[] arr, int l, int h, Random rnd) {
        if (arr == null || l >= h)
            return;
        int pivot = partition(arr, l, h, rnd);
        sortHelper(arr, l, pivot - 1, rnd);
        sortHelper(arr, pivot + 1, h, rnd);
    }

    /**
     * 单路快排partition
     *
     * @param arr
     * @param l
     * @param h
     * @param rnd
     * @param <E>
     * @return
     */
    private static <E extends Comparable<E>> int partition(E[] arr, int l, int h, Random rnd) {
        int p = l + rnd.nextInt(h - l + 1);
//        int p = l + (new Random()).nextInt(h - l + 1);
        swap(arr, l, p);
        int j = l;
        E pivot = arr[l];
        //循环不变量：arr[l+1,j]<pivot, arr[j+1,i-1]>=pivot。
        //(l,j] < pivot;(j,i-1]>=pivot
        //(l,j] < pivot;(j,i)>=pivot
        //哪个更好呢？
        for (int i = l + 1; i <= h; i++) {
            if (arr[i].compareTo(pivot) < 0) {
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, j, l);
        return j;
    }

    /**
     * 双路快排。用两个指针同时遍历。
     * arr(l,i)小于等于pivot, arr(j,h]>=pivot,同时将i和j更新。可以解决单路不适用的“数组元素都相同“的情景。
     *
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort2ways(E[] arr) {
        Random rnd = new Random();
        sort2Helper(arr, 0, arr.length - 1, rnd);
    }

    /**
     * 双路快排实现
     *
     * @param arr
     * @param l
     * @param h
     * @param rnd
     * @param <E>
     */
    private static <E extends Comparable<E>> void sort2Helper(E[] arr, int l, int h, Random rnd) {
        if (arr == null || l >= h)
            return;
        int pivot = partition2(arr, l, h, rnd);
        sort2Helper(arr, l, pivot - 1, rnd);
        sort2Helper(arr, pivot + 1, h, rnd);
    }

    /**
     * 双路快排partition
     *
     * @param arr
     * @param l
     * @param h
     * @param rnd
     * @param <E>
     * @return
     */
    private static <E extends Comparable<E>> int partition2(E[] arr, int l, int h, Random rnd) {
        int p = l + rnd.nextInt(h - l + 1);
//        int p = l + (new Random()).nextInt(h - l + 1);
        swap(arr, l, p);
        int i = l + 1, j = h;
        E e = arr[l];
        while (true) {
            while (i <= j && arr[i].compareTo(e) < 0)
                i++;
            while (i <= j && arr[j].compareTo(e) > 0)
                j--;
            if (i >= j)
                break;
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

    /**
     * 三路快排
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort3ways(E[] arr) {
        Random rnd = new Random();
        sort3Helper(arr, 0, arr.length - 1, rnd);
    }

    /**
     * 双路快排实现
     *
     * @param arr
     * @param l
     * @param h
     * @param rnd
     * @param <E>
     */
    private static <E extends Comparable<E>> void sort3Helper(E[] arr, int l, int h, Random rnd) {
        if (arr == null || l >= h)
            return;
        int p = rnd.nextInt(h-l+1)+l;
        swap(arr,p,l);
        //(l,lt]<v, (lt,i)==v, [gt,h]>v
        int lt = l, i = l+1,gt=h+1;
        E v = arr[l];
        while (i < gt) {
            if (arr[i].compareTo(v) < 0) {
                lt++;
                swap(arr,i,lt);
                i++;
            } else if (arr[i].compareTo(v) == 0) {
                i++;
            } else { //>
                gt--;
                swap(arr,i,gt);
            }
        }
        swap(arr,l,lt);
        //交换后，[l,lt)<v, [lt,i)==v, [gt,h]>v
        sort3Helper(arr,l,lt-1,rnd);
        sort3Helper(arr,gt,h,rnd);
    }

    /**
     * 交换
     *
     * @param arr
     * @param i
     * @param j
     * @param <E>
     */
    private static <E extends Comparable<E>> void swap(E[] arr, int i, int j) {
        E tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }



    public static void main(String[] args) {
        int n = 20000;

        System.out.println("\nRandom Array");
        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);
        Integer[] arr4 = Arrays.copyOf(arr, arr.length);
        SortingHelper.sortTest("QuickSort", arr);
        SortingHelper.sortTest("MergeSort", arr2);
        SortingHelper.sortTest("QuickSort2ways",arr3);
        SortingHelper.sortTest("QuickSort3ways",arr4);

        System.out.println("\nOrdered Array:");
        arr = ArrayGenerator.generateOrderedArray(n);
        arr2 = Arrays.copyOf(arr, arr.length);
        SortingHelper.sortTest("QuickSort", arr);
        SortingHelper.sortTest("MergeSort", arr2);
        SortingHelper.sortTest("QuickSort2ways",arr3);
        SortingHelper.sortTest("QuickSort3ways",arr4);

        System.out.println("\nSame Value Array:");
        arr = ArrayGenerator.generateRandomArray(n, 1);
        arr2 = Arrays.copyOf(arr, arr.length);
        SortingHelper.sortTest("QuickSort", arr);
        SortingHelper.sortTest("MergeSort", arr2);
        SortingHelper.sortTest("QuickSort2ways",arr3);
        SortingHelper.sortTest("QuickSort3ways",arr4);
//        Random Array
//        QuickSort ,n = 20000, time = 0.012471 s
//        MergeSort ,n = 20000, time = 0.012265 s
//        QuickSort2ways ,n = 20000, time = 0.012671 s
//        QuickSort3ways ,n = 20000, time = 0.015086 s
//
//        Ordered Array:
//        QuickSort ,n = 20000, time = 0.006177 s
//        MergeSort ,n = 20000, time = 0.023065 s
//        QuickSort2ways ,n = 20000, time = 0.001930 s
//        QuickSort3ways ,n = 20000, time = 0.007750 s
//
//        Same Value Array:
//        QuickSort ,n = 20000, time = 0.420814 s
//        MergeSort ,n = 20000, time = 0.016125 s
//        QuickSort2ways ,n = 20000, time = 0.001398 s
//        QuickSort3ways ,n = 20000, time = 0.002812 s
//
    }
}
